package datastructure;/*
 *  @类名: SqQueue
 *  @作者: 钟翔 武月月 押琼捷 张玉蓉
 *  @班级：23级网络空间安全一班
 *  @时间: 22024.11.5
 *  @描述:非循环队列，用data<E>数组来存放队列中元素。约定：队头指针为front（实际上是队头元素的前一个位置），
    队尾指针为rear（正好是队尾元素的位置）。初始时置front和rear均为-1（front==rear）元素进队，rear增加1
    元素出队列，front增加1

 */

import java.util.Arrays;

public class SqQueue<E> implements Queues<E>{
    final int InitSize= 5;			//假设初始容量容量为自己设定
    private int size;               //队列容量
    private E [] data;				//存放队列中的元素
    private int front,rear;			//队头队尾指针

    // 构造方法，初始化队列
    public SqQueue() {      //钟翔
        size = InitSize;
        data = (E[]) new Object[size];
        front = rear = -1;
    }

    // 入队操作
    public void enqueue(E item) {       //钟翔
        if (isFull()) {
            expandCapacity();
        }
        rear++;
        data[rear] = item;
    }

    // 出队操作
    public E dequeue() {        //钟翔
        if (isEmpty()) {
            System.out.println("队列为空");
            return null;
        }
        E item = data[front + 1];
        front++;
        if (shouldShrink()) {
            shrinkCapacity();
        }
        return item;
    }

    // 判断队列是否为空
    public boolean isEmpty() {          //张玉蓉
        return front + 1 == rear;
    }

    // 判断队列是否已满
    public boolean isFull() {           //张玉蓉
        return rear == size - 1;
    }

    // 获取队列中的元素个数
    public int getSize() {      //张玉蓉
        return rear - front;
    }

    // 打印队列中的元素
    public void printQueue() {       //张玉蓉
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        System.out.print("队列中的元素：");
        for (int i = front + 1; i <= rear; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    private void expandCapacity() {         //押琼捷
        int newSize = size * 2;
        E[] newData = Arrays.copyOf(data, newSize);
        data = newData;
        size = newSize;
    }

    private void shrinkCapacity() {     //押琼捷
        int newSize = size / 2;
        if (newSize < InitSize) {
            return;
        }
        E[] newData = Arrays.copyOf(data, newSize);
        data = newData;
        size = newSize;
        if (rear < size - 1) {
            rear = rear % size;
        }
        if (front > rear) {
            front = -1;
        }
    }

    private boolean shouldShrink() {        //押琼捷
        return!isFull() && getSize() <= size / 2 && size > InitSize;
    }
}

interface Queues<E> {
    void enqueue(E item);
    E dequeue();
    boolean isEmpty();
}

